<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  
</body>
</html>

<script>
  // 数组的排序
  // 排序，就是把一个乱序的数组，通过我们的处理，让他变成一个有序的数组

  
  // arr.sort(function(a, b) {
  //   return a - b
  // })
  // console.log(arr);
  
  
  // 两个变量交换值的方式
  // var a = 11;
  // var b = 22;
  // var temp;
  // temp = a;
  // a = b;
  // b = temp;
  
  
  // 1. 冒泡排序
  // var arr = [3, 1, 5, 6, 4, 9, 7, 2, 8, 10];
  // var temp;
  // function fn(arr) {
  //   if (!Array.isArray(arr)) return;
  //   for (var j = 0,k = 0; j < arr.length; j++) {
  //     // 主要优化的是比较次数
  //     for (var i = 0; i < arr.length - 1 - j; i++) {
  //       k++;
  //       if (arr[i] > arr[i+1]) {
  //         temp = arr[i];
  //         arr[i] = arr[i+1];
  //         arr[i+1] = temp;
  //       }
  //     }
  //   }
  //   console.log(k);
  //   return arr;
  // }
  // console.log(fn(arr));

  // 时间复杂度(算法一共要执行多少步)
  // 空间复杂度(算法一共要占用多少内存)


  // O(n2)
  // 9 + 8 + 7 + ... + 1 = 45
  // n=10  45
  // n   
  // 1 + 2 + 3 + ... + n-1
  // (1 + n - 1) * (n - 1) / 2
  // n² / 2 - n / 2




  // 2. 选择排序
  // - 先假定数组中的第 0 个就是最小的数字的索引
  // - 然后遍历数组，只要有一个数字比我小，那么就替换之前记录的索引
  // - 知道数组遍历结束后，就能找到最小的那个索引，然后让最小的索引换到第 0 个的位置
  // - 再来第二趟遍历，假定第 1 个是最小的数字的索引
  // - 在遍历一次数组，找到比我小的那个数字的索引
  // - 遍历结束后换个位置
  // - 依次类推，也可以把数组排序好


  // var arr = [3, 2, 5, 6, 4, 9, 7, 1, 8, 10];
  // for (var j = 0; j < arr.length; j++) {
  //   // var minIndex = 0; // 先假设最小值的索引是0
  //   var minIndex = j; // 先假设最小值的索引是0
  //   for (var i = j + 1; i < arr.length; i++) {
  //     if (arr[i] < arr[minIndex]) {
  //       // 遍历以后，如果发现有一个值比当前这个最小值要小，就把这个值的索引记下来
  //       minIndex = i;
  //     }
  //   }
  //   // console.log(minIndex);
  //   // 发现最小值以后就去和第一个元素换位置
  //   var temp;
  //   temp = arr[j];
  //   arr[j] = arr[minIndex];
  //   arr[minIndex] = temp;
  // }
  // console.log(arr);





  

  // 当数组需要进行splice操作的时候，会让我们的数组的长度变短
  // 如果依旧进行i++，那么就会导致跳过一些元素的循环，数组塌陷
  // 解决方案
  // 1. 倒着循环
  // 2. splice之后进行一次i--

  // var arr = [1,5,4,5,3,2,1,2,6,8,3];

  // for(var i = arr.length; i >= 0; i--) {
  //   if (arr[i] < 5) {
  //     arr.splice(i, 1)
  //   }
  // }
  // for(var i = 0; i < arr.length; i++) {
  //   if (arr[i] < 5) {
  //     arr.splice(i, 1);
  //     i--;
  //   }
  // }

  // console.log(arr);










  // 选择排序2
  // var arr = [3, 2, 5, 6, 4, 9, 7, 1, 8, 10];
  // var newArr = [];

  // for (var j = 0; j < arr.length; j++) {
  //   var minIndex = 0;
  //   for (var i = 1; i < arr.length; i++) {
  //     if (arr[i] < arr[minIndex]) {
  //       minIndex = i
  //     }
  //   }
  //   // console.log(minIndex);
  //   newArr.push(arr[minIndex]);
  //   arr.splice(minIndex, 1);
  // }
  
  // console.log(newArr);


  // for (var j = arr.length - 1; j > 0; j--) {
  //   var minIndex = arr.length - 1;
  //   for (var i = 1; i < arr.length; i++) {
  //     if (arr[i] < arr[minIndex]) {
  //       minIndex = i
  //     }
  //   }
  //   // console.log(minIndex);
  //   newArr.push(arr[minIndex]);
  //   arr.splice(minIndex, 1);
  // }
  
  // console.log(newArr);
  

</script>